import java.util.LinkedList;
import java.util.List;

public class FloodFill {

    public static void main(String[] args) {
        FloodFill floodFill = new FloodFill();
        floodFill.wardrobeFinishing(4, 7, 5);
    }

    /**
     * 衣橱整理 剑指 Offer 13. 机器人的运动范围
     */
        int mFinishing, nFinishing, cntFinishing, retFinishing;
        boolean[][] checkFinishing;
        int[] dyFinishing = {0, 1};
        int[] dxFinishing = {1, 0};
        public int wardrobeFinishing(int _m, int _n, int _cnt) {
            mFinishing = _m; nFinishing = _n; cntFinishing = _cnt; retFinishing = 0;
            checkFinishing = new boolean[mFinishing][nFinishing];
            recursion(0, 0);
            return retFinishing;
        }

        void recursionFinishing(int y, int x){
            checkFinishing[y][x] = true;
            retFinishing++;
            for(int i = 0; i < 2; i++){
                int yy = dyFinishing[i] + y;
                int xx = dxFinishing[i] + x;

                if(yy < 0 || yy == mFinishing || xx < 0 || xx == nFinishing || checkFinishing[yy][xx])continue;

                if(getDigitFinishing(yy, xx) > cntFinishing) continue;

                recursionFinishing(yy, xx);
            }
        }

    int getDigitFinishing(int y, int x){
        int n = 0;

        while(y != 0){
            n += y % 10;
            y /= 10;
        }

        while(x != 0){
            n += x % 10;
            x /= 10;
        }
        return n;
    }
    /**
     * 扫雷游戏 八个方向遍历
     */
    int mBoard, nBoard;
    boolean[][] checkBoard;
    char[][] boardBoard;
    int[] dyBoard = {-1, -1, -1, 0, 0, 0, 1, 1, 1};
    int[] dxBoard = {-1, 0, 1, -1, 0, 1, -1, 0, 1};
    int[] ayBoard = {-1, -1, -1, 0, 0, 0, 1, 1, 1};
    int[] axBoard = {-1, 0, 1, -1, 0, 1, -1, 0, 1};
    public char[][] updateBoard(char[][] _board, int[] click) {
        boardBoard = _board;
        mBoard = boardBoard.length;
        nBoard = boardBoard[0].length;
        checkBoard = new boolean[mBoard][nBoard];
        recursionBoard(click[0], click[1]);
        return boardBoard;
    }

    void recursionBoard(int y, int x){
        checkBoard[y][x] = true;
        if(boardBoard[y][x] == 'M'){
            boardBoard[y][x] = 'X';
            return;
        }
        boardBoard[y][x] = 'B';
        //地雷数
        int cm = 0;
        //判断周围一圈
        for(int i = 0; i < 9; i++){
            int yy = y + ayBoard[i];
            int xx = x + axBoard[i];
            if(yy < 0 || yy == mBoard || xx < 0 || xx == nBoard) continue;
            if(boardBoard[yy][xx] == 'M'){
                cm++;
            }
        }

        if(cm != 0){
            boardBoard[y][x] = (char)(cm + '0');
            return;
        }

        for(int i = 0; i < 9; i++){
            int yy = y + dyBoard[i];
            int xx = x + dxBoard[i];
            if(yy < 0 || yy == mBoard || xx < 0 || xx == nBoard || checkBoard[yy][xx]) continue;
            recursion(yy, xx);
        }
    }
    /**
     * 太平洋大西洋水流问题
     */
    int mPacificAtlantic, nPacificAtlantic;
    int[][] heightsPacificAtlantic;
    int[] dyPacificAtlantic = {-1, 1, 0, 0};
    int[] dxPacificAtlantic = {0, 0, -1, 1};

    public List<List<Integer>> pacificAtlantic(int[][] _heights) {
        heightsPacificAtlantic = _heights;
        mPacificAtlantic = heightsPacificAtlantic.length;
        nPacificAtlantic = heightsPacificAtlantic[0].length;

        boolean[][] pacific = new boolean[mPacificAtlantic][nPacificAtlantic];
        boolean[][] atlantic = new boolean[mPacificAtlantic][nPacificAtlantic];

        //pacific
        //上
        for (int x = 0; x < nPacificAtlantic; x++) {
            recursion(0, x, pacific);
        }
        //左
        for (int y = 0; y < mPacificAtlantic; y++) {
            recursion(y, 0, pacific);
        }

        //atlantic
        //右
        for (int y = 0; y < mPacificAtlantic; y++) {
            recursion(y, nPacificAtlantic - 1, atlantic);
        }

        //下
        for (int x = 0; x < nPacificAtlantic; x++) {
            recursion(mPacificAtlantic - 1, x, atlantic);
        }

        List<List<Integer>> ret = new LinkedList<>();
        for (int y = 0; y < mPacificAtlantic; y++) {
            for (int x = 0; x < nPacificAtlantic; x++) {
                if (pacific[y][x] && atlantic[y][x]) {
                    ret.add(List.of(y, x));
                }
            }
        }
        return ret;
    }

    //表示水可以流的位置
    void recursion(int y, int x, boolean[][] check) {
        check[y][x] = true;
        for (int i = 0; i < 4; i++) {
            int xx = x + dxPacificAtlantic[i];
            int yy = y + dyPacificAtlantic[i];

            if (yy < 0 || yy == mPacificAtlantic || xx < 0 || xx == nPacificAtlantic || check[yy][xx]) continue;

            if (heightsPacificAtlantic[yy][xx] >= heightsPacificAtlantic[y][x]) recursion(yy, xx, check);
        }
    }

    /**
     * 被围绕的区域 正难者反
     */
    int mSolve, nSolve;
    boolean[][] checkSolve;
    char[][] boardSolve;
    int[] dySolve = {-1, 1, 0, 0};
    int[] dxSolve = {0, 0, -1, 1};

    public void solve(char[][] _board) {
        boardSolve = _board;
        mSolve = boardSolve.length;
        nSolve = boardSolve[0].length;
        checkSolve = new boolean[mSolve][nSolve];

        for (int i = 0; i < nSolve; i++) {
            if (boardSolve[0][i] == 'O' && !checkSolve[0][i]) {
                recursion(0, i);
            }
            if (boardSolve[mSolve - 1][i] == 'O' && !checkSolve[mSolve - 1][i]) {
                recursion(mSolve - 1, i);
            }
        }

        for (int i = 0; i < mSolve; i++) {
            if (boardSolve[i][0] == 'O' && !checkSolve[i][0]) {
                recursion(i, 0);
            }
            if (boardSolve[i][nSolve - 1] == 'O' && !checkSolve[i][nSolve - 1]) {
                recursion(i, nSolve - 1);
            }
        }

        for (int y = 0; y < mSolve; y++) {
            for (int x = 0; x < nSolve; x++) {
                if (boardSolve[y][x] == 'A') boardSolve[y][x] = 'O';
                else if (boardSolve[y][x] == 'O') boardSolve[y][x] = 'X';
            }
        }
    }

    void recursion(int y, int x) {
        boardSolve[y][x] = 'A';
        checkSolve[y][x] = true;
        for (int i = 0; i < 4; i++) {
            int yy = y + dySolve[i];
            int xx = x + dxSolve[i];
            if (yy < 0 || yy >= mSolve || xx < 0 || xx >= nSolve || checkSolve[yy][xx] || boardSolve[yy][xx] == 'X') {
                continue;
            }
            recursion(yy, xx);
        }
    }

    /**
     * 图像渲染
     */
    int mFloodFill, nFloodFill;
    int[] dyFloodFill = {-1, 1, 0, 0};
    int[] dxFloodFill = {0, 0, -1, 1};
    int[][] imageFloodFill;

    public int[][] floodFill(int[][] _image, int sr, int sc, int color) {
        imageFloodFill = _image;
        mFloodFill = imageFloodFill.length;
        nFloodFill = imageFloodFill[0].length;
        recursion(sr, sc, imageFloodFill[sr][sc], color);
        return imageFloodFill;
    }

    void recursion(int y, int x, int init, int color) {
        if (imageFloodFill[y][x] != init) return;
        imageFloodFill[y][x] = color;
        for (int i = 0; i < 4; i++) {
            int yy = y + dyFloodFill[i];
            int xx = x + dxFloodFill[i];
            if (yy < 0 || yy == mFloodFill || xx < 0 || xx == nFloodFill || imageFloodFill[yy][xx] == color) continue;
            recursion(yy, xx, init, color);
        }
    }


    /**
     * 岛屿的数量  and  岛屿的最大面积
     */
    int mNumIslands, nNumIslands;
    boolean[][] checkNumIslands;
    int retNumIslands;
    char[][] gridNumIslands;
    int[] dyNumIslands = {-1, 1, 0, 0};
    int[] dxNumIslands = {0, 0, -1, 1};

    public int numIslands(char[][] _grid) {
        gridNumIslands = _grid;
        mNumIslands = gridNumIslands.length;
        nNumIslands = gridNumIslands[0].length;
        checkNumIslands = new boolean[mNumIslands][nNumIslands];
        for (int y = 0; y < mNumIslands; y++) {
            for (int x = 0; x < nNumIslands; x++) {
                if (checkNumIslands[y][x]) continue;
                if (gridNumIslands[y][x] - '0' == 1) {
                    recursionNumIslands(y, x);
                    retNumIslands++;
                }
            }
        }
        return retNumIslands;
    }

    void recursionNumIslands(int y, int x) {
        if (gridNumIslands[y][x] - '0' == 0) return;

        checkNumIslands[y][x] = true;
        for (int i = 0; i < 4; i++) {
            int yy = y + dyNumIslands[i];
            int xx = x + dxNumIslands[i];
            if (yy < 0 || yy == mNumIslands || xx < 0 || xx == nNumIslands || checkNumIslands[yy][xx]) continue;
            recursionNumIslands(yy, xx);
        }
    }
}
